
#ifndef __DONGNAOEDU_SORT_H_
#define __DONGNAOEDU_SORT_H_

#include <stddef.h>
#include <stdlib.h>
#include <string.h>

/***********************************************************************************************************
 *
 * 算法描述：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序
 *           错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
 *           这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 *
 * 实现步骤：
 *          1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 *          2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 *          3. 针对所有的元素重复以上的步骤，除了最后一个；
 *          4. 重复步骤1~3，直到排序完成。
 *
 *
 ***********************************************************************************************************/

template <typename T>
void bubble_sort(T a[], size_t size) 
{
    for (int i = 0; i < size; i ++)
    {
        /* 每一次排序之后，此次拍的最后一个元素是最大的 */
        for (int j = 0; j < size - i - 1; j++)
        {
            if (a[j] > a[j+1])
            {
                 T temp = a[j+1];
                 a[j+1] = a[j];
                 a[j]   = temp;
            }
        }
    }
}


/***********************************************************************************************************
 *
 * 算法描述：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序
 *           错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
 *           这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
 *
 * 实现步骤：
 *          1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 *          2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
 *          3. 记录最后一次交换元素的位置（pos），pos之后的位置没有发生交换，那就是已经有顺序的了；
 *          4. 重复步骤1~3，直到排序完成。
 * 时间复杂度：
 *           最优情况：T(n) = O(n)，也就是说如果是已经有顺序的，那么就仅仅需要一趟比较就行
 *           最差情况：T(n) = O(n^2)，
 *           平均情况：T(n) = O(n^2)
 *
 ***********************************************************************************************************/

template <typename T>
void bubblesort_2(T a[], size_t size) 
{
    int i = size - 1;
    while ( i > 0) 
    {
        int pos = 0; //每趟开始时,无记录交换
		
        for (int j= 0; j< i; j++)
        {
            if (a[j]> a[j+1]) 
            {
                pos= j; //记录交换的位置
                T tmp = a[j]; 
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
		
        i = pos; //为下一趟排序作准备
     }
}

/***********************************************************************************************************
 *
 * 算法描述：Selection-sort是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，
 *           存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序
 *           序列的末尾。以此类推，直到所有元素均排序完毕。
 *          
 * 实现步骤：
 *          1. 初始化是无序的状态，第一次排序默认a[0]最小，然后从a[1...n-1]中持续与最小值进行比较，找到
 *             最小值后与a[0]交换；
 *          2. 继续从a[2...n-1]寻找最小值与a[1]交换；
 *          3. 重复排序，直到最后一个元素也有序
 * 时间复杂度：
 *           最优情况：T(n) = O(n^2)
 *           最差情况：T(n) = O(n^2)
 *           平均情况：T(n) = O(n^2)
 *
 ***********************************************************************************************************/
template <typename T>
void select_sort(T a[], size_t size)  
{
    for (int i = 0; i < size; i++)
    {
        int min_index = i;    //每一趟排序开始时，默认最小值是起始值
	
        // 找到最小的数的index
        for (int j = i + 1; j < size; j++)
        {
            if (a[j] < a[min_index])
            {
                min_index = j;
            }
        }
		
        T tmp = a[i];
        a[i] = a[min_index];
        a[min_index] = tmp;
    }
}

/***********************************************************************************************************
 *
 * 算法描述：插入排序对于未排序的的数据在已经排序的序列里插入到合适位置，这个合适位置就是从有序的序列里的最后
 *           一个位置开始往前扫描，如果扫描到一个元素比该元素大（或小），那么该位置的后一个位置就是要插入的位置
 *          
 * 实现步骤：
 *          
 * 时间复杂度：
 *           最优情况：T(n) = O(n^2)
 *           最差情况：T(n) = O(n^2)
 *           平均情况：T(n) = O(n^2)
 *
 ***********************************************************************************************************/
template <typename T>
void insert_sort(T a[], size_t size)
{
    //默认第一个元素是有序的
    for (int i = 1; i < size; i++)
    {
        // 每一趟排序，拿出未排序的第一个元素
        T value = a[i];   

        // 从有序数组里最后一个元素开始比较，如果比value大，
        // 那么该值就往后移动一个位置，否则就找到插入的位置为j+1
        int j = i - 1;
        for (; j > -1; j--)
        {
            if (a[j] > value)
            {
                a[j + 1] = a[j];
            }
            else
            {
                break;
            }
        }
		
        //插入到该位置
        a[j+1] = value;
    }
}

/***********************************************************************************************************
 *
 * 算法描述：对insert_sort的改进，就是在查找的使用可以采用折半查找
 *           第一个突破O(n^2)的排序算法。
 * 实现步骤：
 *          
 * 时间复杂度：
 *           最优情况：T(n) = O(n^2)
 *           最差情况：T(n) = O(n^2)
 *           平均情况：T(n) = O(n^2)
 *
 ***********************************************************************************************************/
template <typename T>
void insert_sort_2(T a[], size_t size)
{
    //默认第一个元素是有序的
    for (int i = 1; i < size; i++)
    {
        // 每一趟排序，拿出未排序的第一个元素
        T value = a[i];   

        //折半查找
        int left  = 0;
        int right = i - 1;
        while (left <= right)
        {
            int middle = ( left + right ) / 2;
            if (value > a[middle])
            {
                left = middle + 1;
            }
            else
            {
                right = middle - 1;
            }
        }
	
        // 从已经排好的序的最后一个元素开始移动元素，直到找到的那个位置
	for (int j = i - 1; j >= left; j--) 
        {
            a[j + 1] = a[j];
        }
	
        a[left] = value;
    }
}

/***********************************************************************************************************
 *
 * 算法描述：1959年Shell发明；第一个突破O(n^2)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，
 *           它会优先比较距离较远的元素。希尔排序又叫缩小增量排序，先将整个待排序的记录序列分割成为若干子序列
 *           分别进行直接插入排序。
 *
 * 实现步骤：
 *          1. 选择一个增量序列gap[1]，gap[2]，…，gap[k]，其中gap[i]>gap[j](i > j)，gap[k]=1；
 *          2. 按增量序列个数k，对序列进行k 趟排序；
 *          3. 每趟排序，根据对应的增量gap[i]，将待排序列分割成若干长度为size/gap[i] 的子序列，分别对各子表
 *             进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 *
 * 时间复杂度：
 *           最优情况：T(n) = O(n*log2n)
 *           最差情况：T(n) = O(n*log2n)
 *           平均情况：T(n) = O(n*logn)
 *
 ***********************************************************************************************************/
template <typename T>
void shell_sort(T a[], size_t size)
{
    int gap = size / 2; //gap的值  
    while (gap > 0)
    {
        //对于gap所分的每一个组
        for (int x = 0; x < gap; x++) 
        {  
	    //进行插入排序，其中x + gap是该分组第二个元素
            for (int i = x + gap; i < size; i = i + gap) 
            {
                int temp= a[i];
                int j;  
                for (j = i - gap; j >= 0;j = j - gap)
                {
                    /* 如果比待插入的元素大，则往后移动一个位置，否则退出移位的循环 */
                    if (a[j] > temp)
                    {
                        a[j+ gap] = a[j];
                    }
                    else
                    {
                        break;
                    }
                }
                
                //插入待插元素
                a[j+ gap] = temp;  
            }
        }
        
        gap = gap / 2;//每次都将gap的值减半   
  
    }  
}


/***********************************************************************************************************
 *
 * 算法描述：非递归实现 -- 自底向上
 *           将数组中的相邻元素两两配对。用merge函数将他们排序，
 *           构成n/2组长度为2的排序好的子数组段，然后再将他们排序成长度为4的子数组段，
 *           如此继续下去，直至整个数组排好序。。
 * 实现步骤：
 *          
 * 时间复杂度：
 *           最优情况：T(n) = O(n)
 *           最差情况：T(n) = O(n*logn)
 *           平均情况：T(n) = O(n*logn)
 *
 ***********************************************************************************************************/
template <typename T>
void merge_sort(T a[], size_t size)
{
	// 将原数组划分为left[min...max] 和 right[min...max]两部分
    int i, left_min, left_max, right_min, right_max, next;
    int *tmp = (int*)malloc(sizeof(int) * size);

    if (tmp == NULL)
    {
        return;
    }

    for (i = 1; i < size; i = i * 2) // i为步长，1,2,4,8……
    {
        for (left_min = 0; left_min < size - i; left_min = right_max)
        {
            right_min = left_max = left_min + i;
            right_max = left_max + i;

            if (right_max > size)
                right_max = size;

            //进行归并，归并的结果放在tmp数组里
            next = 0;
            while (left_min < left_max && right_min < right_max)
            {
                if ( a[left_min] > a[right_min] )
                {
                    tmp[next] = a[right_min];
                    right_min ++;
                }
                else
                {
                    tmp[next] = a[left_min];
                    left_min ++;
                }
                next ++;
            }

            /* 没有归并完的，放在序列的最后 */
            while (left_min < left_max)
            {
                a[--right_min] = a[--left_max];
            }

            /* 已经归并的，放在序列的前部 */
            while (next > 0)
            {
                a[--right_min] = tmp[--next];
            }
        }
    }

    free(tmp);
}

/***********************************************************************************************************
 *
 * 算法描述：快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是
 *           处理大数据最快的排序算法之一了。
 *           通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别
 *           对这两部分记录继续进行排序，以达到整个序列有序。
 *
 * 实现步骤：
 *          1. 从数列中挑出一个元素，称为 "基准"（pivot）；
 *          2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数
 *		       可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 *          3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 *
 * 时间复杂度：
 *           最优情况：T(n) = O(n)
 *           最差情况：T(n) = O(n*logn)
 *           平均情况：T(n) = O(n*logn)
 *
 ***********************************************************************************************************/
template <typename T>
void quick_sort(T a[], size_t size)
{
    int left, right, pivot, tmp;
    if (size < 2)  return;

	// 设定中间元素为基准
    pivot = a[size / 2];

	//对元素进行分区，从左边分区寻找比基准大的元素，从右边分区寻找比基准小的元素，然后交换
    for ( left = 0, right = size -1; ; left++, right--) 
	{
        while (a[left] < pivot)
            left++;
        while (pivot < a[right])
            right--;
        if ( left >= right)
            break;
		
        tmp = a[left]; 
		a[left] = a[right]; 
		a[right] = tmp;
    }
	
	//递归对左分区快排
	quick_sort( a, left);
	
	//递归对右分区进行快排
    quick_sort( a + left, size - left);
}

/***********************************************************************************************************
 *
 * 算法描述：是指利用堆这种数据结构所设计的一种排序算法。二叉堆是一个完全二叉树的结构，并同时满足堆的性质：
 *           1. 即子结点的键值或索引总是小于（或者大于）它的父节点。
 *           2. 父节点和子节点满足某种序列
 *
 * 实现步骤： 
 *         1. 将初始待排序关键字序列(R0,R1....Rn-1)构建成大顶堆，构建的过程就是每次把R[i]的元素向上调整，
 *            此堆为初始的无序区；
 *         2. 将堆顶元素R0与最后一个元素R[n-1]交换，此时得到新的无序区(R0,R2,......Rn-2)和新的有序区(Rn),
              且满足R[0,1...n-2]<=R[n-1]；
 *         3. 在第二步后，堆可能无序了，需要对堆逐步向下调整，一直满足堆得特性才行。
 *         4. 循环第二步和第三步，直到堆得最后一个元素调整完毕。
 *
 * 时间复杂度：
 *           最优情况：T(n) = O(n*logn)
 *           最差情况：T(n) = O(n^2)
 *           平均情况：T(n) = O(n*logn)
 *
 ***********************************************************************************************************/
template <typename T>
void heap_sort(T a[], size_t size)
{
    for (int i = 1; i < size; i++)
    {
        //逐步向上调整，通过向上调整，构建大根堆
        T value = a[i];
        int current_index = i;
        while(current_index > 0)
        {
            int parent_index = (current_index - 1) / 2;
            if (a[parent_index] < value)
            {
                T parent_value = a[parent_index];
                a[parent_index] = a[current_index];
                a[current_index] = parent_value;
            }
            else
            {
                break;
            }
            current_index = parent_index;
        }
    }

    // 每次把堆顶的元素与a[i]交换，然后堆开始逐步向下调整
    for(int i = size; i > 0; i --)  
    {  
        T tmp = a[i];
        a[i] = a[0];
        a[0] = tmp;
		
        int parent_index = 0;
        int child_index = parent_index * 2 + 1;  // left child
        while(child_index + 1  < i)
        {
            /* select largest one of the two children to exchange with parent  */
            if (a[child_index] < a[child_index + 1])
            {
                child_index ++;
            }
   
            /* if parent's value less than child's value, exchange them */
            if(a[parent_index] < a[child_index])
            {
                T value = a[parent_index];
                a[parent_index] = a[child_index];
                a[child_index] = value;
            }
            else
            {
                break;
            }
            parent_index = child_index;
            child_index  = parent_index * 2 + 1;  // left child
        }
    }
}

/***********************************************************************************************************
 *
 * 算法描述：计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序
 *           数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
 *           它是最快的排序算法，但是因为其对所排序的元素必须要是整数，所以限制了其的应用
 *
 * 实现步骤：       
 *         1. 找出待排序的数组中最大和最小的元素；(Lee哥在这里偷懒了，直接使用了RANDMAX，表示排序的元素是0~RANDMAX)
 *         2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
 *         3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；这个累加就是让C[i]计数了有多少个元素
 *            少于或者等于i的元素，方便了反向输出元素时找到元素存放在数组a中的下标。
 *         4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
 *
 * 时间复杂度：
 *           线性时间
 *           最优情况：T(n) = O(n + RANDMAX)
 *           最差情况：T(n) = O(n + RANDMAX)
 *           平均情况：T(n) = O(n + RANDMAX)
 *
 * 缺点：1. 元素不能是负数；
 *       2. 额外申请了内存，如果元素值很大，怎么办？
 *
 ***********************************************************************************************************/
#define RANDMAX  100

template <typename T>
void count_sort(T a[], size_t size)
{
    //计数数组，用于统计数组array中各个不同数出现的次数   
    T *counts = (T *) calloc(RANDMAX, sizeof(T));
    
	//用于存放已经有序的数列
    T *storteds = (T *) calloc(size, sizeof(T));
  
    //统计数组a中各个不同数出现的次数，循环结束后counts[i]表示数值i在a中出现的次数
    int index = 0;  
    for (index = 0; index < size; ++index) 
	{  
        counts[a[index]]++;
    }  
  
    //统计数值比index小的数的个数，循环结束之后counts[i]表示a中小于等于数值i的元素个数  
    for (index = 1; index < RANDMAX; ++index) 
	{  
        counts[index] += counts[index - 1];  
    }
  
    for (index = size - 1; index >= 0; --index)
	{  
        //因为数组的起始下标为0，所以要减一  
        storteds[counts[a[index]] - 1] = a[index];
		
        //这里减一是为了保证当有多个值为a[index]的元素时，后出现的值为a[index]的元素  
        //放在后面，也就是为了保证排序的稳定性  
        --counts[a[index]];  
    }
  
    memcpy(a, storteds, size * sizeof(int));  
    free(storteds);  
    free(counts);
}



#endif
